Published: 2022-07-26
I recently stumbled across a networking article mentioning an XOR operation performed by a host when deciding if packets to an IP-address should be sent to the default gateway or not. I wanted to learn more about this XOR operation but searching the internet yielded no useful result. This blog post is therefore an attempt to explain this.
Starting off, any device that joins an IPv4 or IPv6 network is configured with an IP-address and a Subnet mask. The IP-address is used to communicate with other devices, the mask is used to determine if the device we want to communicate with is connected to the same subnet as us.
If the other device exists outside of our own subnet, the packet must be sent to the default gateway who routes it towards the other device. If the other device is connected to the same subnet as our device, we can send the packet directly without having to pass it through the default gateway, saving resources on the default gateway.
So, let's say our device is configured with IP-address 10.0.0.10 and a /24 subnet mask. If we want to communicate with 10.0.0.20 then we can communicate directly without disturbing the default gateway. If we want to communicate with 8.8.8.8 or 10.0.2.20 that both are outside of our subnet, we must send the packet to the default gateway. We all know this, but how does the device know this?
The answer is Bitwise XOR and AND operators. The XOR is used to compare the local IP-address and the destination IP-address, creating an XOR result. The XOR result is then compared to the subnet mask using an AND operator to determine if the other device is inside or outside the subnet. Let's dig deeper.
Paraphrased from Wikipedia, a bitwise operation is an operation that happens at the bit-level of any string or number. This is a very fast and efficient action that can run on any processor and is much faster than performing actions such as addition, division or multiplication.
Our IPv4-addresses and subnet masks are actually just 32-bit numbers presented in a funny way. The IP-address 8.8.8.8 is here presented in the format of an IPv4 address but can also be presented in decimal as 134744072. If you run the command ping 134744072 on Windows or Linux you will see that they generate ping packets to 8.8.8.8. The same IP-address can be presented in binary format, displaying the value of every single bit. More on that below.
Compare:
0101 (decimal 5)
XOR 0011 (decimal 3)
--------------------
= 0110 (decimal 6)
The above example shows the XOR operator in action. XOR is short for Exclusive OR and it compares each bit of two numbers to identify which bits have different values. If the compared bits have different values the XOR result for that bit will be a 1; otherwise 0.
The AND operator will compare individual bits of two numbers and set the result to 1 if both compared bits have the value 1. If one, or both, have the bit-value set to 0, the AND-operator result will be 0.
0101 (decimal 5)
AND 0011 (decimal 3)
--------------------
= 0001 (decimal 1)
Using these two highly efficient XOR/AND operators, the host can determine if the destination IP is inside the local subnet or not. The first part is doing an XOR compare on the local and destination IP-addresses. The XOR result is then compared with the subnet mask using an AND operator. If the AND result is all-zeroes, the two IP-addresses belong to the same subnet.
Checking packet from 10.0.0.10/24 to 10.0.0.20:
XOR operator:
10.0.0.10 = 00001010.00000000.00000000.00001010
10.0.0.20 = 00001010.00000000.00000000.00010100
------------------------------------------------
XOR result = 00000000.00000000.00000000.00011110
AND operator:
XOR result = 00000000.00000000.00000000.00011110
Subnetmask = 11111111.11111111.11111111.00000000
------------------------------------------------
AND result = 00000000.00000000.00000000.00000000
Because the AND result is an all-zeroes number,
we can determine that both IP-addresses belong to
the same local subnet.
Checking packet from 10.0.0.10/24 to 10.0.2.20:
XOR operator:
10.0.0.10 = 00001010.00000000.00000000.00001010
10.0.2.20 = 00001010.00000000.00000010.00010100
------------------------------------------------
XOR result = 00000000.00000000.00000010.00011110
AND operator:
XOR result = 00000000.00000000.00000010.00011110
Subnetmask = 11111111.11111111.11111111.00000000
------------------------------------------------
AND result = 00000000.00000000.00000010.00000000
^
|
match!
This time the AND result is not all-zeroes,
the destination IP-address is therefore not in the
same subnet as us. Send packet to Default Gateway.
That is basically it! An all-zeroes AND result means both devices are in the same subnet and can communicate directly, otherwise the packet should go to the default gateway.
When researching this I did some testing with Python, which I thought I could share below. It uses the netaddr library as it allows me to do bitwise comparisons that wouldn't be possible if I used strings, as the strings would otherwise have to be converted to integers first.
from netaddr import IPAddress
src = IPAddress("10.0.0.10")
dst = IPAddress("10.0.2.20")
mask = IPAddress("255.255.255.0")
xor_result = src ^ dst # ^ is the python bitwise XOR operator
and_result = xor_result & mask # & is the bitwise AND operator
print(xor_result.bits())
print(and_result.bits())
if and_result is False:
print(f"{dst} is inside the same subnet, send directly.")
else:
print(f"{dst} is outside the subnet, send to default gateway.")
I hope this blog post was as fun to read as it was to write. I always assumed the host would consult its routing table to determine whether the packet must be sent to default gateway or not, but it seems that is not (always?) the case.
Sources and inspirations:
https://www.dpstele.com/dps/protocol/2001/jul-aug/ip-routing.php
https://realpython.com/python-bitwise-operators/
https://en.wikipedia.org/wiki/Bitwise_operation